Computer graphics uses a variety of methods to generate two-dimensional representations of a three-dimensional scene. For example, a three-dimensional scene represented as a plurality of geometric primitives (e.g., points, lines, triangles, quads, meshes, etc.) may be rasterized to intersect the geometric primitives with a projection plane and then shaded to calculate a color for one or more pixels of the projection plane based on the rasterization. Alternatively, another technique for generating two-dimensional representations of the three-dimensional scenes is to perform ray-tracing. As is known in the art, ray-tracing is a technique that includes the operation of sending out rays from a particular viewpoint and intersecting the rays with the geometry of the scene. When an intersection is detected, lighting and shading operations may be performed to generate a color value for a pixel of the projection plane intersected by the ray. Additionally, other rays may be generated based on the intersected primitives that contribute to the color of the intersected pixel or other pixels.
Because the number of geometric primitives in a scene may be quite large (e.g., on the order of millions of triangles, etc.) and the number of rays generated to test for intersection against those primitives is also large (e.g., on the order of millions or even billions of rays, etc.), a data structure may be generated to increase the efficiency of performing the intersection tests. The data structure may be referred to as a spatial acceleration structure because the topology of the structure enables efficient searching of a three-dimensional space. One such data structure is a tree, such as a k-d (k-dimensional) tree, an R*-tree, or a bounding volume hierarchy. When an intersection test is performed for a given ray, a tree traversal may be performed in order to efficiently test the ray against all of the primitives included in the scene.
Conventional trees may define each of the nodes in the tree relative to a global coordinate system. The global coordinate system is used to locate points in a three-dimensional space, and may be associated with an origin O. Each point in the three-dimensional space may then be defined using a set of coordinates, such as an x-coordinate that specifies a location of the point relative to the x-axis, a y-coordinate that specifies a location of the point relative to the y-axis, and a z-coordinate that specifies a location of the point relative to the z-axis. When nodes of the tree are encoded in a data structure, attributes of the nodes, such as a bounding volume associated with the node, may be encoded using geometry specified relative to the global coordinate system. For example, an axis-aligned bounding box for a node may be specified by encoding six values that represent the locations of the six planes of the axis-aligned bounding box relative to the global coordinate system (e.g., a minimum and maximum plane located on the x-axis, a minimum and maximum plane located on the y-axis, and a minimum and maximum plane located on the z-axis). Conventionally, each value is encoded using a fixed-width encoding technique. For example, each value may be specified as a 32-bit floating point value.
One shortcoming of traditional acceleration structures is that the spatial resolution of data encoded within the structure is limited by a precision of the fixed-width encoding technique. When the extents of the scene become large, such limitations may make it difficult to effectively represent fine details. Effectively, all of the bits of the fixed-width encoding are used to represent coarse details of the scene, while none of the bits are used to represent fine details of the scene. For example, individual blades of grass may be difficult to differentiate using values encoded with the fixed-width encoding technique if the extents of the scene are many orders of magnitude larger than the extents of a blade of grass (e.g., the scene models a city, etc.). Thus, there is a need for addressing these issues and/or other issues associated with the prior art.